package lrucache;

import java.util.HashMap;
import java.util.Map;

/**
 * Creat with IntelliJ IDEA
 * Description: 自己实现 LRUCache
 * User:WZW
 * Date:2022-10-19
 * Time:23:52
 */
public class MyLRUCache {
    static class DlinkNode {
        public int key;
        public int val;
        public DlinkNode prev;
        public DlinkNode next;

        public DlinkNode(){}

        public DlinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return "{ key=" + key +", val=" + val +'}';
        }
    }

    public DlinkNode head;
    public DlinkNode tail;
    public int usedSize;
    public Map<Integer, DlinkNode> cache;
    public int capacity;//容量

    public MyLRUCache(int capacity) {
        head = new DlinkNode();
        tail = new DlinkNode();
        head.next = tail;
        tail.prev = head;
        cache = new HashMap<>();
        this.capacity = capacity;
    }

    /**
     * 存储元素
     * @param key
     * @param val
     */
    public void put(int key, int val) {
        //1.查找当前key是否存储过
        DlinkNode node = cache.get(key);
        //2.如果没有存储过
        if (node == null) {
            //2.1 实例化一个节点
            DlinkNode dlinkNode = new DlinkNode(key,val);
            cache.put(key,dlinkNode);
            addToTail(dlinkNode);
            usedSize++;
            if (usedSize > capacity) {
                DlinkNode remNode = removeHead();
                cache.remove(remNode.key);
            }
        } else {
            //3. 存储过
            //更新value值
            node.val = val;
            //将节点移到尾巴
            moveToTail(node);
        }
    }

    private void moveToTail(DlinkNode node) {
        //删除该节点
        removeNode(node);
        //将该节点添加到尾巴中
        addToTail(node);
    }

    /**
     * 删除指定节点
     * @param node
     */
    private void removeNode(DlinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }


    private DlinkNode removeHead() {
        DlinkNode del = head.next;
        head.next = del.next;
        del.next.prev = head;
        return del;
    }

    /**
     * 将节点添加到链表尾部
     * @param node
     */
    private void addToTail(DlinkNode node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    public int get(int key) {
        DlinkNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToTail(node);
        printNodes("get ");
        return node.val;
    }

    private void printNodes(String str) {
        System.out.println(str+": ");
        DlinkNode cur = head.next;
        while (cur != tail) {
            System.out.println(cur);
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MyLRUCache lruCache = new MyLRUCache(3);
        lruCache.put(100,10);
        lruCache.put(110,11);
        lruCache.put(120,12);
        System.out.println("获取元素");
        System.out.println(lruCache.get(110));
        System.out.println(lruCache.get(100));
        System.out.println("存放元素,会删除头节点，因为头节点是最近最少使用的: ");
        lruCache.put(999,99);
    }
}
